A. Field of the Invention
The present invention relates generally to data transfer and, more particularly, to systems and methods for allocating bandwidth for the processing of packets within a network device, such as a router.
B. Description of Related Art
Conventional networks typically include routers that route packets from one or more sources to one or more destinations. A packet carries data or control information and can be transmitted through a network. A router is a switching device that receives packets at input ports and, based on destination or other information included in the packets, routes the packets through output ports to final or intermediary destinations. Conventional routers determine the proper output port for a particular packet by evaluating header information included in the packet.
Conventional routers include buffers to support a particular bandwidth. If the input network traffic exceeds the bandwidth of the router, the router may drop packets. Expanding the bandwidth depends on a number factors, including the input line rate, the speed of the output determination process, and the blocking characteristics of the switching mechanisms of the router. Router bandwidth also relates to the processing power of the router. The processing power typically depends on the size of the memory (i.e., bigger and faster systems require larger memory capacities) and the ability of the router to determine where to route packets.
A key problem in designing routers is making them scale to higher aggregate bandwidths. To process higher bandwidths in a single conventional router, the size and configuration of the router typically has to be modified or redesigned. The process of modifying a router to increase bandwidth usually entails tedious design processes with the risk that the new design will not perform as intended or integrate well with other routers in the network, the outlay of resources (both monetary and human), as well as potential time delays.
One technique for increasing router bandwidth is to build a router with multiple packet processing components that operate in parallel. Incoming packet streams are divided among the packet processing components, processed, and then reassembled into the packet stream.
When dividing the packet stream among the number of packet processing components, one issue that arises is how to divide the packet stream so that the work load is evenly distributed among the packet processing components. One conventional solution to this problem is to use a packet sprayer to equitably distribute the packets to the processing components.
The sprayer maintains a counter for each packet processing component. The counters keep track of the packet stream being forwarded to each packet processing component by counting the number of bytes in the stream. An incoming packet is sprayed to the packet processing component corresponding to the counter with the lowest stream count value. In this manner, the sprayer balances the number of bytes transmitted to the packet processing components.
One problem with such a conventional sprayer is that, although it balances byte count very well, it does not necessarily do a good job of balancing packet count. For example, if there are four packet processing components, and the incoming traffic pattern includes three 4500-byte packets followed by 100 45-byte packets, the above-described sprayer may spray one of the 4500-byte packets to each of the first three packet processing components and the 100 45-byte packets to the last packet processing component. Because each individual packet requires a certain amount of processing regardless of its size, the packet processing component that receives the 100 smaller packets will have significantly degraded performance relative to the other three packet processing components. Thus, in this situation, the sprayer will not effectively load balance the packet processing components.
Therefore, there exists a need for systems and methods that increase the bandwidth for processing of packets in a router by more effectively load balancing across multiple parallel packet processing components.